package com.googlecode.gaal.analysis.impl;

import com.googlecode.gaal.analysis.api.IntervalSetBuilder;
import com.googlecode.gaal.data.api.IntervalSet;
import com.googlecode.gaal.data.impl.IntervalBitSet;
import com.googlecode.gaal.suffix.api.BinaryIntervalTree;
import com.googlecode.gaal.suffix.api.SuffixArray;
import com.googlecode.gaal.suffix.api.BinaryIntervalTree.BinaryNode;

public class ProperIntervalSetBuilder implements IntervalSetBuilder {

    @Override
    public <E extends BinaryNode<E>, T extends SuffixArray & BinaryIntervalTree<E>> IntervalSet<E> buildIntervalSet(
            T tree) {
        IntervalSet<E> bwtSet = new IntervalBitSet<E>(tree);
        traverse(bwtSet, tree.top(), 0);
        return bwtSet;

    }

    private <E extends BinaryNode<E>> void traverse(IntervalSet<E> bwtSet, E interval, int parentLcp) {
        if (!interval.isTerminal()) {
            int lcp = interval.lcp();
            E left = interval.leftChild();
            E right = interval.rightChild();
            if (lcp != parentLcp) {
                bwtSet.add(interval);
            }
            traverse(bwtSet, left, lcp);
            traverse(bwtSet, right, lcp);
        }
    }

}
